

\documentclass{article}

%% PACKAGES $$
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb}
\usepackage{listings}
\usepackage{float}
\usepackage{cite}
\usepackage{subfig}
\usepackage[pdftex]{graphicx}
\usepackage{algorithmic}
\usepackage{multicol}
\usepackage{tikz}
\usepackage{multirow}
\usepackage{enumerate}

%% COMMANDS %%

\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\newcommand{\tuple}[1]{\ensuremath{\left \langle #1 \right \rangle }}

\definecolor{OliveGreen}{rgb}{0,0.6,0}
\lstset{
    language=python,
    basicstyle=\ttfamily\small,
    commentstyle=\color{OliveGreen}}
\newcommand{\cfrg}[1]{{\lstinline!#1!}}


\begin{document}

\title{The Domination Game \\ \large{Game Programming MSc Artificial Intelligence}}
\author{Thomas van den Berg \& Tim Doolan \\ \small{\texttt{thomas.g.vandenberg@gmail.com, tim.doolan@gmail.com}} \\ \small{Teacher: Frank Aldershoff}}

\date{\today}

\maketitle

\section{Introduction}
As a Profile Project we completely rebuilt the so-called ``Domination Game''; a game engine that was created to facilitate experimentation with multi-agent systems in the AAMAS (Autonomous Agents and Multi-Agent Systems) course. Our main motivation for this was to improve the speed, reliability and predictability of the simulation results. After finishing this project, it turned out that simulator needed quite a bit more work before it could be used by the AAMAS course. We decided to complete those challenges for our Game Programming project, most important of which were making a render loop that could be turned off completely for speed and adding a usable game interface. Therefore this report focuses more on the technical aspects of creating a game engine and rendering the frames, as other decisions have already be covered in our previous report. In order to make the game actually fun to play and allow for some additional insight in tactics, we also added the ability for a user to \emph{directly} control the agents in the simulation.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{illustrations/screenshot.png}
\end{figure}


\section{The Game}
The game is a simple computer strategy game; two teams of agents compete for occupation of control points. To score they have to reach these control points and defend the enemy from getting close to them. There is ammo scattered around the field that the agents can pick up and use to shoot the other team's agents. When an agent gets shot it is reset to the starting position on the field. 

\subsection{Movement}
The game is divided into timesteps and at each timestep all agents of both teams can perform actions simultaneously. An action consists of a turn (any value between $\frac{\pi}{3}$ and $\frac{-\pi}{3}$), followed by the option to shoot in the current facing direction (max 60 pixels away) and finally moving in the current facing direction (max 40 pixels). Action commands can be provided in two ways, using the manual control or by coding an agent file to be used by each of the agents. Both types of control will be elaborated on in Section \ref{control}.

\subsection{Score}
On each map there are 3 control points, which are initially neutral. If an agent moves over the control point, it becomes his team's color. For each timestep a point belongs to a team a point is added to the teams score and subtracted from the opposite team (both teams start with 500 points). When a team has reached 1000 points, they win the game. If two opposing agents both occupy a control point, the control point becomes neutral, and neither team scores. If there are more than two agents on the point, the team with the majority gains control. This way, agents are rewarded for preventing the other team from scoring, and sending additional agents to a control point is usually beneficial.

\subsection{Shooting}
The ammo points hold an ammo pack which contains 3 bullets. When picked up, packs respawn on the ammo point after 20 timesteps. Shoot actions cost 1 bullet. If an agent from the opposing team is hit by the shot, he is instantly transferred back to his team respawn area. Agents in the respawn area are forced to wait 10 timesteps before they can move again.

\subsection{Maps}
The maps to play on are generated randomly; this is so the game will be varied and programmed agents can't be hardcoded with specific positions. The basic approach for map generation is to add ammo and control points randomly. Then a fixed number of wall sections are also added randomly to locations in the field. Each wall is only added if there are still paths connecting  all ammo, spawn and control points. These paths are computed using the connectivity graph and pathfinding tools we also coded for the game (they are covered more extensively in section \ref{control}). We use this method on one half of the field, and then mirror it for the other team to create a fully symmetric playing field for fairness. 


\begin{figure}[H]
  \begin{center}
    \subfloat{\includegraphics[width=0.25\textwidth]{illustrations/field-01.png}} 
    \hspace{0.05\textwidth}
    \subfloat{\includegraphics[width=0.25\textwidth]{illustrations/field-02.png}} 
    \hspace{0.05\textwidth}
    \subfloat{\includegraphics[width=0.25\textwidth]{illustrations/field-03.png}} \\
  \vspace{0.2cm}
  \begin{minipage}{0.9\textwidth}
    \caption{Examples of randomly generated fields. Black dots indicate ammo locations, green squares are the control points. \label{fig:random_maps}}
  \end{minipage}
  \end{center}
\end{figure}


\section{Physics Engine}

By implementing a \emph{physics engine} like one that is often employed in games, we hoped to make the game faster, fairer, and easier. The goal of such a physics engine is to handle collisions between objects in a somewhat realistic manner. All kinds of physical phenomena are widely used in computer games (e.g. inertia, friction, elasticity). We chose only a small subset of these features, i.e. those features that ensure that objects keep some of their velocity after a collision. This makes it less likely for agents to suffer great penalties from small mistakes. For example: if an agent wants to maneuver around a corner, but it hits the wall, it won't be stopped dead in its tracks, but instead `slides' around the obstacle. Additionally, by using efficient methods that are widely used for physics simulation, we can speed up the simulation. We chose to code our own physics engine so we could cut out all the overhead, and make it as fast as possible given our requirements.

\subsection{The World}
The game world is assumed to consist only of \emph{rectangular} and \emph{circular} objects. Additionally, all objects are always \emph{axis-aligned}. These assumptions allow for efficient implementations of collision detection and handling. Objects do not have mass, so while they can have a certain velocity, this is does not lead to inertia. Where the objects' movement leads to collisions, they are \emph{separated}. Objects can also be \emph{non-solid}, meaning they are allowed to move through each other, but will register collisions. 

\subsection{Sort-and-Sweep}
In a naive implementation, each pair of objects would have to be checked to see whether they collide, leading to $O(n^2)$ checks, and then the resulting collisions have to be solved. However, there are many clever implementations to perform this `broad-phase' checking more efficiently. One of the methods that is simple to implement is called \emph{sort-and-sweep}. This algorithm sorts the objects along an arbitrary axis. It then iterates over the objects in order and checks whether they overlap on this axis. Because the objects are sorted, once an object is found not to overlap with the next one, it does not have to be checked against any further objects in the sorted list. Additionally, because objects are likely not to move very much between two timesteps, re-sorting the list is usually fast.


\begin{table}
    \begin{center}
    \begin{minipage}{12cm}
    \begin{algorithmic}
      \STATE $O \gets$ list of objects \COMMENT{All objects}
      \STATE $P \gets $ empty list \COMMENT{Possibly colliding pairs}
      \STATE $sort(O)$ using $min\_x$
      \FOR{$i = 1 \to |O|$}
        \FOR{$j = i \to |O|$}
          \IF{$max\_x(O_i) < min\_x(O_{j})$}
            \IF{$min\_y(O_{j}) < max\_y(O_i)$ and $min\_y(O_i) < max\_y(O_{j})$}
              \STATE Add $\tuple{O_i, O_j}$ to $P$
            \ENDIF
          \ELSE 
            \STATE break
          \ENDIF
        \ENDFOR
      \ENDFOR
      \STATE Handle collided pairs of objects in $P$
    \end{algorithmic}
    \end{minipage}
    \end{center}
    \centering
    \caption{Simple sort-and-sweep. \label{tbl:sort_and_sweep}}
\end{table}


\begin{figure}[H]
    \centering
        \subfloat[Bounding Boxes]{\includegraphics[width=0.22\textwidth]{illustrations/sort-and-sweep-01.png}} 
        \hspace{0.1\textwidth}
        \subfloat[Sort And Sweep]{\includegraphics[width=0.22\textwidth]{illustrations/sort-and-sweep-02.png}}\\
    \vspace{0.2cm}
    \begin{minipage}{0.9\textwidth}
        \caption{Illustrations for Table \ref{tbl:sort_and_sweep}. \label{fig:sort_and_sweep}}
    \end{minipage}
\end{figure}


\subsection{Separation}
When we know which pairs' bounding boxes collide, we can compute whether we need to separate them. Rectangular objects will always collide when their bounding boxes collide, but circles might not. If two objects collide, we separate them with the smallest movement possible, usually this means moving them in the opposite direction of the colliding surface normal, shown in Figure \ref{fig:separation}. If one of the objects is indicated not to be movable, the other object is moved the full distance. Otherwise, both objects are moved half of the separation vector, in opposite directions.

\subsection{Substeps}
Obviously, separating the objects might cause them to overlap with \emph{other} objects, this is why we repeat the separation \emph{substep} a number of times, hoping that the system will settle in some kind of convergent state. We repeat this substep 10 times within each simulation step. Additionally, we tolerate penetrating objects if the penetration distance is small (c.q. less than a pixel).

\begin{figure}[H]
  \begin{center}
  \begin{minipage}{0.95\textwidth}
    \vspace{0.5cm}
    \subfloat[Separating two rectangles.]{\includegraphics[width=0.2\textwidth]{illustrations/separation-01.png}} 
    \hspace{0.05\textwidth}
    \subfloat[Separating a circle and a rectangle.]{\includegraphics[width=0.2\textwidth]{illustrations/separation-02.png}} 
    \hspace{0.05\textwidth}
    \subfloat[Separating a circle and a rectangle.]{\includegraphics[width=0.2\textwidth]{illustrations/separation-03.png}} 
    \hspace{0.05\textwidth}
    \subfloat[Separating two circles.]{\includegraphics[width=0.2\textwidth]{illustrations/separation-04.png}} 
    \caption{Different kind of separations that can be computed. \ref{tbl:sort_and_sweep}. In (a) the rectangles are separated along vector A or B, depending on which is shorter. In (b) the circle is treated like a rectangle. In (c) the rectangle's corner is treated like a zero-radius circle. \label{fig:separation}}
  \end{minipage}
  \end{center}
\end{figure}

\section{Rendering}
Rendering this game is a bit different from the way rendering works in normal games, because we wanted the game to be able to run \emph{without} the renderer, and run as fast as possible when doing so. The greatest obstacle here was that the simulation operates in discrete steps, but we want to render those steps smoothly over multiple frames. One example of this is that the shooting is computed as a single-pass operation where dead tanks are removed from the game, however, we want to render this over multiple frames during which projectiles fly through the air and tanks explode.

\subsection{Timesteps}
To make this work, we did not implement a standard ``update, render'' loop, but rather interspersed calls to the renderer within the simulation code. As you can see in Table \ref{tbl:timesteps}, the number of rendering steps is still linked to the number of physics substeps ($S$), we cannot render the animation at a finer time-resolution than is computed by the physics engine. We could skip frames, but the game runs at a pleasant speed so we chose not to.

\begin{table}[H]
	\centering
	\begin{tabular}{ll}
		\textbf{With Renderer} & \\
		\multirow{2}{*}{$R$ Times} & Rotate by $\frac{a}{R}$\\
		& \texttt{render()}\\
		\hline
		Once & Compute shooting\\
		\hline
		$H$ Times & \texttt{render()}\\
		\hline
		\multirow{2}{*}{$S$ Times} & Physics substep\\
		& \texttt{render()}\\
		\hline
		 
	\end{tabular}
	\begin{tabular}{ll}
		\textbf{Without Renderer} \\
		Once & Rotate by ${a}$\\
		\\
		\hline
		Once & Compute shooting\\
		\hline
		\\
		\hline
		$S$ Times & Physics substep\\
		\\
		\hline
		 
	\end{tabular}
	\caption{	\label{tbl:timesteps}
One game step consists of these substeps. In the game, all of $R$, $H$ and $S$ are equal to 10, and the game runs at 60 FPS.}
\end{table}

In every call to the renderer (indicated by \texttt{render()} in Table \ref{tbl:timesteps}), the current state of the game is passed. This contains enough information since it includes the intermediate state information generated by the physics substeps. There is one exception, between frames of the \emph{shooting} phase, there is no difference in game state, since there is no intermediate ``dying'' state for tanks. In this situation we simply play a fixed animation for all tanks that have died. 

\subsection{Blitting in Pygame}
The game state consists of the locations and angles for every object (tanks, walls, ammo, etc). Because we only use the bitmap rendering component from Pygame, we need to rotate and \emph{blit} (bit-block image transfer) an image to the buffer for each object. A much simplified version is shown in Listing \ref{lst:rendering}. In reality we need to take into account that the size of the rotated sprite is different, that some objects can be blitted without rotating, and that we can pre-render the map, since the locations of the walls don't change. The walls are pre-rendered to a surface, because they don't change from frame to frame. Then, at each render step, this map is first copied to the frame buffer, after which all the objects are added on top of it.

\begin{lstlisting}[%
    caption=The (simplified) render procedure,%
    label=lst:rendering,%
    frame=tb,%
    gobble=2]{}
  for o in game.objects:          
      # Fetch the right texture for this object
      bmp = textures[o.type]
      # Create a rotated version
      bmp = pygame.transform.rotate(bmp, -o.angle)
      # Blit it to the viewport
      viewport.blit(bmp, dest=(o.x,o.y))
\end{lstlisting}

\subsection{Autotiling}
Often in 2D games, tiles on the map (e.g. walls) look different depending on what tiles are adjacent to them (e.g. a straight wall section versus a corner). To automatically use the right kind of texture for each tile, we used the ``autotile'' algorithm. This algorithm detects what kind of tile there is to the top, bottom, left, and right of each tile, and sets a corresponding bit to \textbf{1} in that tile's texture index. 

\noindent\begin{minipage}[t]{0.5\linewidth}\centering
\begin{tabular}{l|r}
        TOP & \texttt{0001} \\
        RIGHT & \texttt{0010} \\
        BOTTOM & \texttt{0100} \\
        LEFT & \texttt{1000} \\
        \hline
        TOP and BOTTOM & \texttt{0101}\\
        etc
\end{tabular}
\end{minipage}
\begin{minipage}[c]{0.5\linewidth}\centering
\begin{figure}[H]
    \centering
    \subfloat[Without autotiling]{\label{fig:autotile-wo} \includegraphics[width=0.4\textwidth] {illustrations/autotile-wo.png} }
    \subfloat[With autotiling]{\label{fig:autotile-with} \includegraphics[width=0.4\textwidth] {illustrations/autotile-with.png} }
\end{figure}
\end{minipage}
\vspace{1cm}

This gives each tile a texture index between 0 and 16 ($2^4$), so if we create 16 different tiles and order them like Figure \ref{fig:autotiles}, we can easily grab the right one and draw it to the buffer.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{illustrations/autotiles.png}
    \caption{\label{fig:autotiles}The 16 needed tiles.}
\end{figure}
    
\section{Controling the agents}\label{control}

\subsection{Tools}
We added some out-of-the-box tools to game, in order to make common low level tasks easier in the game. The most important of these tools is the navigation graph created from the random map. This graph indicates connectivity between areas, allowing a standard pathfinding algorithm to be used by the agents. In addition to that, there are a number of functions to perform common geometrical operations, and a fast implementation of $A^*$. Because users don't need to write their own implementations of these standard tasks, they can start working on the core tasks faster when coding an agent and because the implementations are efficient we cut back on simulation time.

\subsubsection{Navigation}
In order to navigate around the map using an algorithm like $A^*$, some kind of navigation mesh or graph is needed such that at least
one node is visible from each point on the map. One solution would be to subdivide the map into convex regions, and define
connectivity between these regions, however this could yield sub-optimal navigation, as the agents have to go through the `gates'
between the regions. We wanted to create a navigation mesh that is both automatically generated based on the map and yields near 
optimal navigation. Our algorithm is as follows (and illustrated in Figure \ref{fig:create_nav_mesh}).

\begin{figure}[H]
    \centering
\subfloat[Step I]{\includegraphics[width=0.22\textwidth]{illustrations/creating-a-mesh-01.png}}
\hfil
\subfloat[Step II]{\includegraphics[width=0.22\textwidth]{illustrations/creating-a-mesh-02.png}}
\hfil
\subfloat[Step III]{\includegraphics[width=0.22\textwidth]{illustrations/creating-a-mesh-03.png}}
\hfil
\subfloat[Step IV]{\includegraphics[width=0.22\textwidth]{illustrations/creating-a-mesh-04.png}}
\caption{Creating a navigation graph.}
\label{fig:create_nav_mesh}
\end{figure}

\begin{enumerate}[I]
    \item Expand all walls by some amount larger than the agent radius\footnote{Putting the nodes further from the walls yields smoother navigation around corners.} and put nodes on the corners of these expanded walls.
    \item Remove nodes that are inside or on the edge of another expanded wall.
    \item Perform \emph{raycasts} to determine all nodes that have a straight connecting line between them.
    \item Starting with the longest connection, remove each connection if there is an alternative shortest route that is less than $(1+\delta)$ times its length.
\end{enumerate}

\subsection{Coding an agent}
All team agents run the same code file, coded in Python. At each timestep all agents asked for an action, which should be simple a tuple of rotation, shooting (boolean) and movement. To make the problem more interesting an agent can only act on local observations in a radius of 100 pixels. The agents are passed an observation object containing the relative location of all relevant objects like opponents, ammo, walls and control points. The action tuple can then be computed as result of the observation, game history and the tool functions like $A*$.


\begin{figure}[H]
  \begin{center}
    \subfloat{\includegraphics[width=0.7\textwidth]{illustrations/nav-graph.png}} 
    \vspace{0.2cm}
  \begin{minipage}{0.9\textwidth}
    \caption{The navigation graph is drawn on this image. For every point on the field, there is at least one node that can be reached in a straight line, and the edges indicate which nodes have straight lines connecting them. \label{fig:nav_mesh}}
  \end{minipage}
  \end{center}
\end{figure}

\subsection{Manual Control}
Agents can also be manually controlled, so you can try and beat your coded agents. Agents can be selected for control by clicking a agent or dragging a box around multiple agents. Selected agents can be given a queue of waypoints to follow. One click will reset the queue to a single point, additional points can be added to the queue using \textit{Shift} click. Timesteps move continuously in the game, but \textit{Space} can be used to pause the game, so multiple agents can be controlled in a single timestep. Navigation is done internally using the pathfinding tools and shooting is done automatically when the agent has ammo and an opponent is in range. When an agent dies, it's old queue is restored, so all the player has to do is refine individual paths for agents. This should provide an interesting high-level game, namely finding an effective combination of agent paths and this also might help with insights on how to code a better opponent.

\section{Conclusion}
Programming a game engine that is to be used as a high performance user-friendly framework is a daunting task. By thinking carefully about the final design of the project we managed to keep the scope small and implement the desired features in the best possible way. Development went smoothly since we had set clear goals and because we chose a programming language that we were both familiar with. In the end, the code was successfully used and well received by the students of this year's AAMAS course. The ``manual-control'' add-on that we implemented is a fun gimmick, but the game is only a playable prototype when used in this fashion.

\section*{Notes}
Please refer to the README in the code package for information on how to play the game. The most recent framework code can be found on http://git.io/dominationgame.


\end{document}


% ONE IMAGE
% \begin{figure}[H]
%     \vspace{0.5cm}
%     \centering
%     \begin{minipage}{0.9\textwidth}
%         \includegraphics[width=\textwidth]{images/results-comparison.png}
%         \caption{Results for each of the experiments. \label{fig:results-comparison}}
%     \end{minipage}
% \end{figure}


% TWO IMAGES IN A FIGURE
% \begin{figure}[H]
%     \vspace{0.5cm}
%     \centering
%         \subfloat{\includegraphics[width=0.4\textwidth]{images/wrong-class-ugly.png}} \hspace{0.04\textwidth}
%         \subfloat{\includegraphics[width=0.4\textwidth]{images/wrong-class-nice.png}}\\
%     \begin{minipage}{0.84\textwidth}
%         \caption{The page on the left was wrongly classified as beautiful because photos are excluded from the color palette extraction. The page on the right was wrongly classified as ugly because the smooth graphic adds a lot of colors to the extracted palette. \label{fig:miss-experiment-aesthetics}}
%     \end{minipage}
% \end{figure}